package leetcode.editor.cn;

import java.util.ArrayList;
import java.util.List;

/**
 * @id: 22
 * @title: 括号生成
 */
 
//数字 n 代表生成括号的对数，请你设计一个函数，用于能够生成所有可能的并且 有效的 括号组合。 
//
// 有效括号组合需满足：左括号必须以正确的顺序闭合。 
//
// 
//
// 示例 1： 
//
// 
//输入：n = 3
//输出：["((()))","(()())","(())()","()(())","()()()"]
// 
//
// 示例 2： 
//
// 
//输入：n = 1
//输出：["()"]
// 
//
// 
//
// 提示： 
//
// 
// 1 <= n <= 8 
// 
// Related Topics 字符串 动态规划 回溯 
// 👍 1971 👎 0

public class P22GenerateParentheses {
    public static void main(String[] args) {
        Solution solution = new P22GenerateParentheses().new Solution();
        // todo 
        List<String> result = solution.generateParenthesis(3);
        System.out.println(result);
    }
    
//leetcode submit region begin(Prohibit modification and deletion)
class Solution {
    /**
     *  如果dp[i]<0就不通过
     *  动态规划
     * @param n
     * @return
     */
//    public List<String> generateParenthesis(int n) {
//        List<String> list = new ArrayList<>();
//        if (n <= 0) {
//            list.add("");
//            return list;
//        }
//        for (int i=0 ; i < n ; i++) {
//            int k = n-i-1;
//            List<String> results = generateParenthesis(k);
//            List<String> results1 = generateParenthesis(i);
//            for(String str1 : results) {
//                for (String str2 : results1) {
//                    String result = "(" + str1 + ")" + str2;
//                    list.add(result);
//                }
//            }
//        }
//        return list;
//    }

    /**
     * 递归剪支
     * @param n
     * @return
     */
    public List<String> generateParenthesis(int n) {
        List<String> ans = new ArrayList<>();
        dfs(ans,"", n, 0, 0);
        return ans;
    }

    private void dfs(List<String> ans, String path, int n, int l, int r) {
        if (l < r) {
            return;
        }
        if (l == n && r == n) {
            ans.add(path);
            return;
        }
        if (l+1 <= n) {
            dfs(ans, path + "(", n,l+1, r);
        }
        if (l > r) {
            dfs(ans, path + ")", n, l, r+1);
        }
    }
}
//leetcode submit region end(Prohibit modification and deletion)


}